1. Field of the Invention
The present invention relates to a navigation system, a route search server, a route search method, and a route search program that can search and guide an optimum route from a departure location to a destination location and, more particularly, to a navigation system, a route search server, a route search method, and a route search program that enables searching an optimum route through a one-time route searching process in a case where several destination or departure locations exist.
Route searching for several destination locations or departure locations refers to route searching for certain locations having a number of possible approaches or entry points, such as a theme park, an event site, or a station of a vehicular means of transportation, and further includes route searching for a point of interest (POI), such as a convenience store or a gas station near a current location or a destination location.
2. Description of the Related Art
Conventionally, a navigation device and a navigation system are widely known to be configured to determine possible routes from a designated departure location to a desired destination location to guide users.
The abovementioned navigation device has been practically applied as a car navigation device incorporated in a car providing route guide information to drivers, while the above mentioned navigation system has been practically applied as a communication type navigation system, which sends a route search and guide request to a route search server by means of a mobile phone functioning as a navigation terminal and receives the result in response to the request to provide route guide service.
In particular, the abovementioned communication type navigation system uses a mobile terminal, such as a mobile phone as a navigation terminal, and is applied as a navigation system for pedestrians. The navigation system designed for pedestrians preferably includes a route guide function in respect of transportation facilities. The navigation system for pedestrians provides traveling and walking route searching and route guide information using road network data and accumulates transportation facility routes as well as timetable data in the route search server as traffic network data.
This type of navigation system for pedestrians is equipped with a function for providing route guides from a designated train departure station to a desired train destination station (candidate trains for boarding) in addition to the function of searching and providing walking route guides. In addition, this navigation system includes a traffic guide network which receives and displays information on accessible means of transportation routes and timetables, available trains and the like from an information distribution server without searching for walking routes.
Further, this kind of navigation system is also equipped with a route search system which searches and provides route guides from a designated departure location to a desired destination location using aircraft, trains, electric trains, or buses. Such a route search system generally searches for routes based on route searching conditions or the user's requirements such as departure date and time schedules, departure locations, destination locations, arrival time and the like.
In other words, the navigation system refers to the provision of traffic network data consisting of route and timetable data pertaining to each of the abovementioned transportation facilities compiled into a database to sequentially search available transportation routes from a designated departure location to a desired destination location including required transfers, and one or more prospective transportation route guides (pertaining to trains, for example) conforming to route searching requirements, which generally relate to travel time, frequency of transfers, fare and the like.
Using the above mentioned road network data to search for travel routes from a certain departure location to a particular destination location, the system calculates the total travel cost in terms of distance or time and determines the minimum cost route which is deemed to be the optimum route and draws up route guide data.
Aside from providing information on the optimum route, the route guide data includes map data and guidance data. In compliance with a search request, route guide data is retrieved from a guide data storage facility and displayed on a display means.
Using a GPS receiver incorporated in the navigation device, a route guide and a mark indicating the current location of the navigation device are generally superposed on a scaled map in such manner that the current location indicator is located in the center of the display screen.
When information given on locational positions using the GPS receiver is in error, such as when a current location deviates from a guided route, a route matching process ensues to shift the current location onto the guided route. Alternatively, corrective route matching occurs or a map matching process takes place to bring the current location to the nearest road on the map.
Also, the route guide data includes a guiding point such as an intersection or a landmark, and so forth. When voice guidance data, such as a voice message saying “An intersection is located 300 meters ahead. Please turn left” is introduced at the guiding point, the same is reproduced and outputted via a speaker.
The above-mentioned navigation system and route search method are disclosed in Japanese Unexamined Patent Publication No. 2000-258184 (refer to FIG. 4) and entitled “Method and Device for Searching Traffic Network Route”.
Using a computer, the route search navigation system under the abovementioned patent publication searches for walking zones and available transportation facilities at minimum cost in accordance with a label determination method, whereby determined routes from a departure location to a destination location are represented as road and traffic network data in which locations are represented as nodes and routes between adjacent nodes are represented as links.
On the other hand, under the route search method disclosed in the abovementioned patent publication, straight line distances from a departure location or a destination location to respective stations of available transportation facilities are obtained as routes using latitude/longitude information, and the average cost is calculated using the straight line distances obtained as variables.
In addition, a walking route is determined by retrieving information regarding the stations of all available means of transportation with the average cost being calculated within a pre-determined cost range. The walking route obtained is incorporated into the route traffic network of the particular transportation facility to form an integrated traffic network and thereby enable the computer to determine a route under desired cost conditions in accordance with the label determination method.
In searching for available walking and transport routes, the user may find that a particular station has a number of entry points and is thus accessible in a number of ways. This situation has been handled in a well-known route search method disclosed in Japanese Unexamined Patent Publication No. 2003-182578 and entitled “Optimum Route Searching Device and Method (see FIG. 9 and FIG. 10), which searches the shortest walking route from a departure location to the nearest station, as well as the shortest walking route from the station nearest to the destination location to the destination location.
Under the above-mentioned patent application, the optimum route search device, with the aid of an optimum route search means, determines one or more departure station candidates near the departure location and one or more destination station candidates near the destination location, using road, data and timetable data pertinent to the particular transportation facility in accordance with the searching order stipulating the searching conditions such as departure location, destination location, and scheduled departure time and date. In addition, the optimum route search device is configured to search for the optimum route incorporating both walking and transportation routes from among combinations of the departure station candidates and the destination station candidates to enable the user to move within the shortest timeframe from the departure location to the destination location according to specified searching conditions. Further, in the situation where the departure or destination station candidate is accessible in quite a number of ways, the optimum route search device is configured to search the optimum route by designating a single access nearest the departure location as the reference location of the departure or destination station candidate.
FIGS. 9 and 10 are typical illustrations showing the conventional route searching concept embodied in the optimum route search device disclosed in Japanese Unexamined Patent Publication No. 2003-182578. FIG. 9 is a typical illustration of the conventional concept for searching a route from a departure location (START) to the station nearest to the departure location and its entry points. FIG. 10 is a typical illustration of the conventional concept for searching a route from the station nearest to the destination location and its exit points leading to the destination location (GOAL).
In conducting route searching from a departure location to a destination location to determine an electric train route by searching the stations nearby, the optimum route search device (as shown in FIG. 9), sequentially searches the shortest walking routes RT1 to RT4, RT5, and RT6 from a departure location (START) to stations ST1 and ST2 near the departure location (START) and their entry accesses A1 to A4, A5, and A6 respectively. Accordingly, the number of searching times for the walking routes corresponds to the number of entry accesses.
Next, as shown in FIG. 10, the optimum route search device sequentially searches the shortest walking routes RP1, RP2, RF1, and RF2 from stations ST3 and ST4 near the destination location (GOAL), and their exit accesses B1, B2, B3, and B4 leading to the destination location (GOAL), respectively. Thus, the number of searching times for the walking routes corresponds to the number of exit points. In addition, in FIGS. 9 and 10, L1 to L4 denote electric train routes, and R0 denotes a radius indicating the range for extracting stations ST1 and ST2 near the departure location (START) and the stations ST3 and ST4 near the destination location (GOAL).
In addition to the above-mentioned function of route searching from a route search server where the destination and departure locations are specified as route searching conditions, the navigation system may also be capable of providing route options under various conditions even without designating a destination location. For example, a user may be looking for a parking lot near certain facilities since the vehicle should be parked. In this case, any parking lot adjacent to or closest to the targeted facility may be designated as a destination location.
The navigation system which makes such route searching possible has been disclosed in Japanese Unexamined Patent Publication No. 2003-057057 entitled “Method and System for Retrieving Information on Parking Lot and Program” (refer to paragraphs [0089], [0090] and FIG. 3, FIG. 6). The system for retrieving information on parking lots is configured such that when a network navigation center searches for routes according to specified route searching conditions from a navigation terminal, the network navigation center retrieves information on a number of parking lots near the designated destination location, searches for the shortest route to each parking lot and then guides the user to the nearest parking lot.
In addition, the network navigation center can also provide route information pertaining to a specific area such as a theme park or an exposition site (refer to FIG. 11 as an example). As shown in FIG. 11, three gates G1 to G3 are provided in the specific area or event site. Generally, a user will recognize the entire area as a destination location without regard to the number of gates therein and request for the nearest route leading to such gate or gates from a certain departure location.
In this case, similar to the method disclosed in Japanese Unexamined Patent Publication No. 2003-057057 of retrieving information on parking lots, a conventional route search server extracts gates G1 to G3 provided in the specific area requested to be searched, searches for the corresponding route from a departure location to each of gates G1 to G3, and provides for a guide in respect of the shortest route or recommends several routes ranked in order of proximity in relation to the departure location.